BZOJ 1119 SLO

Description

对于一个1-N的排列(ai),每次你可以交换两个数ax与ay(x<>y),代价为W(ax)+W(ay) 若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。

Input

第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。 2<=n<=1000000 100<=wi<=6500 1<=ai,bi<=n ai各不相等,bi各不相等 (ai)<>(bi) 样例中依次交换数字(2,5)(3,4)(1,5)

Output

一个数,最小代价。

Sample Input

6
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1

Sample Output

11200

Solution

这些位置组成一个置换群
这不是置换水题么
直接取一个置换里面最小的换
然后就又错了(╯‵□′)╯ノ┻━┻
还有没有狗,还有没有狗!
看题解发现漏了一种情况,可以换一个全局最小代价的元素进来,最后再换回去
还是太弱了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>

#define maxn 1000000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

ll ans;
int a[maxn],b[maxn],pos[maxn];
int vis[maxn],mini[maxn],w[maxn],num[maxn];
int n;

int main()
{

#ifndef ONLINE_JUDGE
freopen("1119.in","r",stdin);
freopen("1119.out","w",stdout);
#endif
scanf("%d",&n);
mini[0]=INT_MAX;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
mini[0]=min(mini[0],w[i]);
}
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
pos[b[i]]=i;
}
for(int i=1;i<=n;i++)
if( !vis[i] ){
ll sum=w[a[i]];
vis[i]=1,num[i]=1,mini[i]=w[a[i]];
int k=pos[a[i]];
while( k!=i ){
vis[k]=1,sum+=w[a[k]];
num[i]++,mini[i]=min(mini[i],w[a[k]]);
k=pos[a[k]];
}
ans+=min((ll)mini[i]*(num[i]-2),(ll)mini[0]*(num[i]+1)+mini[i])+sum;
}
printf("%lld",ans);
return 0;
}